package algorithms.a04heap;

import algorithms.utis.AlgorithmsUtis;
import algorithms.utis.SortTestHelper;

import java.util.Arrays;

/**
 * 最大堆排序
 *
 * @author 王昊然
 * @create 2018-02-09 8:55
 **/
public class MaxHeapSort {

    /**
     * 最简单方式
     * 遍历数组，一个个插入空的最大堆，然后再一个个从最大堆取出放到新的数组里
     *
     * @param arr
     * @date: 2018/2/9 8:56
     * @author: 王昊然
     */
    public static void sort1(Comparable[] arr) {

        int n = arr.length;

        MaxHeap<Comparable> maxHeap = new MaxHeap<>(n + 1);

        for (int i = 0; i < n; i++) {
            maxHeap.insert(arr[i]);
        }

        for (int i = n - 1; i >= 0; i--) {
            arr[i] = maxHeap.extractMax();
        }
    }


    /**
     * 方法1优化，使用heapify
     * 原理：最大堆最后一个元素的父元素，是最后一个有子节点的元素，从该元素开始向上做shiftDown即可，再一个个extractMax取出
     *
     * @param arr
     * @date: 2018/2/9 8:56
     * @author: 王昊然
     */
    public static void sort2(Comparable[] arr) {

        int n = arr.length;

        MaxHeap<Comparable> maxHeap = new MaxHeap<>(arr);

        for (int i = n - 1; i >= 0; i--) {
            arr[i] = maxHeap.extractMax();
        }
    }

    /**
     * 原地堆排序 最优方式
     * 因在原来的arr上直接排序，最大值从0开始了
     * 原理：先将arr转为一个最大堆，然后不停将0位置的元素和最后位置的元素交换，最后位置的指针向前移动
     *
     * @param arr
     * @date: 2018/2/11 22:31
     * @author: 王昊然
     */
    public static void sort(Comparable[] arr) {

        int n = arr.length;

        //nt begin = (n-2)/2最后一个非叶子节点下标
        for (int begin = (n - 2) / 2; begin <= 0; begin--) {
            shiftDown(arr, begin);
        }

        //将最大值和最后元素交换，同时最后元素下标前移
        for (int end = n - 1; end > 0; end--) {
            if (arr[0].compareTo(arr[end]) > 0) {
                AlgorithmsUtis.swap(arr, 0, end);
                shiftDown(arr, 0);
            }
        }


        MaxHeap<Comparable> maxHeap = new MaxHeap<>(arr);

        for (int i = n - 1; i >= 0; i--) {
            arr[i] = maxHeap.extractMax();
        }
    }

    //p为parent下标
    private static void shiftDown(Comparable[] arr, int p) {

        int n = arr.length + 1;//最后一个元素的下标

        Comparable pvalue = arr[p];

        //默认最大值的下标是左叶子: 2*p + 1
        while (2 * p + 1 <= n) {

            int maxi = 2 * p + 1;
            int right = maxi + 1;//右叶子节点

            if (right <= n && arr[right].compareTo(arr[maxi]) > 0) {
                maxi = right;
            }

            if (arr[p].compareTo(arr[maxi]) >= 0) {
                break;
            }

            arr[maxi] = arr[p];
            p = maxi;
        }

        arr[p] = pvalue;
    }

    public static void main(String[] args) {
        //对一个数组使用堆排序
        Integer[] arr = SortTestHelper.generateRandomArray(22000, 0, 50000);
        Integer[] arr1 = Arrays.copyOf(arr, arr.length);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);

        System.out.println("第一次执行忽略");
        SortTestHelper.testSort(MaxHeapSort.class, arr, "sort1");
        SortTestHelper.testSort(MaxHeapSort.class, arr, "sort2");
        SortTestHelper.testSort(MaxHeapSort.class, arr);
        System.out.println("-------------------------");


        SortTestHelper.testSort(MaxHeapSort.class, arr1, "sort1");
        SortTestHelper.testSort(MaxHeapSort.class, arr2, "sort2");
        SortTestHelper.testSort(MaxHeapSort.class, arr3);
    }
}
